package com.lhcai.lc.category.slidingwindow;

/**
 * 713. 乘积小于 K 的子数组
 * 滑动窗口
 *
 * @author liuhuaicai
 * @since 2024-10-19 11:18
 */
public class Lc713 {
    public static void main(String[] args) {
        Lc713 lc713 = new Lc713();
        System.out.println(lc713.numSubarrayProductLessThanK(new int[]{10, 9, 10, 4, 3, 8, 3, 3, 6, 2, 10, 10, 9, 3}, 19));
    }

    public int numSubarrayProductLessThanK(int[] nums, int k) {
        int count = 0;
        int left = 0;
        int prod = 1;
        for (int right = 0; right < nums.length; right++) {
            // 外层循环中，结尾始终是right,不符合时需要left追赶
            // 到right的累计乘积
            prod *= nums[right];
            // 不符合条件时，左侧追赶右侧
            while (left <= right && prod >= k) {
                prod = prod / nums[left];
                left++;
            }
            // 以right为结尾的子数组
            count += right - left + 1;
        }
        return count;
    }

    // 暴力循环  超出时间限制
    // 93 / 98 个通过的测试用例
//    public int numSubarrayProductLessThanK(int[] nums, int k) {
//        int count = 0;
//        for (int i = 0; i < nums.length; i++) {
//            long sum = 1;
//            for (int j = i; j >= 0; j--) {
//                sum *= nums[j];
//                if (sum > 0 && sum < k) {
//                    count++;
//                }
//            }
//        }
//        return count;
//    }
}
